// https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
// Created by ade on 2022/7/18.
//

#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:

    vector<int> mid;
    vector<int> post;

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        mid.assign(inorder.begin(), inorder.end());
        post.assign(postorder.begin(), postorder.end());
        return build(0, post.size() - 1, 0, mid.size() - 1);
    }

    /**
     *
     * @param low1 int 后序
     * @param high1 int 后序
     * @param low2 int 中序
     * @param high2 int 中序
     * @return
     * {9,15,7,20,3}; 后序
     * {9,3,15,20,7}; 中序
     */
    TreeNode *build(int low1, int high1, int low2, int high2) {
        if (low1 > high1 || low2 > high2) return nullptr;

        TreeNode *s = new TreeNode(post[high1]);
        int midIndex = low2;
        for (; midIndex <= high2; midIndex++) {
            if (mid[midIndex] == post[high1]) {
                break;
            }
        }

        s->left = build(low1, low1 + (midIndex - low2) - 1, low2, midIndex - 1);
        s->right = build(low1 + (midIndex - low2), high1 - 1, midIndex + 1, high2);
        return s;
    }

    void show(TreeNode *head) {
        if (head) {
            cout << head->val << ",";
            show(head->left);
            show(head->right);
        }
    }
};

int main() {
    Solution so;
    vector<int> post = {9, 15, 7, 20, 3};
    vector<int> mid = {9, 3, 15, 20, 7};
    /*vector<int> pre = { 3,9,20,15,7 };
    vector<int> mid = { 9,3,15,20,7 };*/
    auto res = so.buildTree(mid, post);
    //cout << res->right->right->val << endl;
    //cout << res->right->val << endl;
    so.show(res);
    return 0;
}